package leetcode_1_20;

import java.util.*;

public class findMedianSortedArrays_4 {
    /**
     *  4.1，寻找两个正序数组交集的中位数
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double r;
        Set<Integer> set=new TreeSet<>();
        for(int i: nums1){
            set.add(i);
        }
        for(int i: nums2){
            set.add(i);
        }
        List list= Arrays.asList(set.toArray());
        //a 用来判定新数组是否是偶数个
        boolean a=set.size()%2==0 ? true:false;
        if (a)  r=((double)(int)list.get(list.size()/2)+(double)(int)list.get(list.size()/2-1))/2;  //是则找到中间两个/2
        else r=(double)((int)list.get(list.size()/2));                      //否则找到中间哪个返回
        return r;
    }

    /**
     *  4.2，寻找两个正序数组的中位数 ,普通解法
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        double r;
        List list= new ArrayList();
        for(int i: nums1){
            list.add(i);
        }
        for(int i: nums2){
            list.add(i);
        }
        Collections.sort(list);
        //a 用来判定新数组是否是偶数个

        //分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用。
        // 加入 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身
        r=( (double)(int)list.get( (list.size()+1)/2 -1 )+(double)(int)list.get( (list.size()+2)/2 -1) )/2;

//        boolean a=list.size()%2==0 ? true:false;
//        if (a)  r=((double)(int)list.get(list.size()/2)+(double)(int)list.get(list.size()/2-1))/2;  //是则找到中间两个/2
//        else r=(double)((int)list.get(list.size()/2));                      //否则找到中间哪个返回
        return r;
    }

    /**
     *  4.2，寻找两个正序数组的中位数 , 满足时间复杂度O(log(m+n))
     *  避免产生新的数组从而增加时间复杂度
     * @param nums1
     * @param nums2
     * @return
     */
    public  static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        double r = 0;
        int i = 0 ,  j = 0 ;
        int m=nums1.length,n=nums2.length;
        r=(
                (double)findKeyth( nums1 ,i , nums2 , j ,( m + n + 1 )/2 )+
                        (double)findKeyth( nums1 , i , nums2 , j ,(m + n + 2 )/2 )
        ) /2;
        return r;
    }

    /**
     * 寻找两个数组的第k个数字
     * @param nums1
     * @param i nums1的起始位置
     * @param nums2
     * @param j nums2的起始位置
     * @param k 需要寻找第 k 个元素
     *  思路：因为两个数组都是正序排列，采用二分法，在两个数组拿到第k/2 个元素。
     *          通过不断递进，两个数组的第  k/2 个元素也在变化。
     *          第 k/2 的数字小的那个数组，说明它的前 k/2 个元素同时小于两边 第k/2 个元素之后的元素
     *          并且还不是这 k 个元素中的最大。
     *          那么说明我们要找的数字肯定不在这个数组前K/2个数字，所以我们可以将其前K/2个数字去掉
     *          去掉之后， k=k-k/2= k/2;, 重复进行，k=1 时，小的那个即为结果
     *          若其中一个数组已无元素，直接从另一个数组剩下的元素中中找当前第k个元素即可
     * @return
     */
    public static int findKeyth(int[] nums1, int i, int[] nums2, int j, int k){
        int m=nums1.length,  n=nums2.length;
        if (i >= m)  return nums2[ j + k - 1 ];                                 //如果已经超出nums1 的范围，直接从 nums2 找对应元素, 直接nums2起始位置 j 加上第几个元素即可
        if( j >= n)   return nums1[ i + k - 1 ] ;
        if( k == 1 ){
            int r=nums1[i] > nums2[j] ? nums2[j] : nums1[i];
            return r;
        }
        int leftVal=  ( i + k / 2 - 1 ) < m ? nums1[ i + k / 2 - 1 ] : 100001;   // i + k / 2 - 1未超出 nums1 边界，则直接赋值，
        // 超出则说明 nums2 的前 k/2 个元素肯定不包含，可以赋予leftVal最大值使直接去除nums2 的前 k/2 个元素
        int rightVal= ( j + k / 2 - 1 ) < n ? nums2[ j + k / 2 - 1 ] : 100001;

        if (leftVal > rightVal)  // nums1 此时第k/2 的元素大于 nums2 此时第k/2 的元素
            j += k / 2;                                                              // 将 nums2 的起始元素后移
        else i += k / 2;                                                          // 将 nums1 的起始元素后移

        return findKeyth(nums1,   i,  nums2 , j , k- k/2);
    }


}
